package lib

func init() {
	Probs = append(Probs, Problem{
		Num:         268,
		Discription: "找出包含n个数字的数组缺失的那一个数",
		Level:       1,
		Labels: map[string]int{
			"空间复用": 1,
		},
	})
}

func MissingNumber(nums []int) int {
	n := len(nums)
	for i := 0; i < n; i++ {
		if nums[i] == i {
			continue
		}

		//注意值可能越界
		for nums[i] < n && nums[nums[i]] != nums[i] {
			nums[i], nums[nums[i]] = nums[nums[i]], nums[i]
		}
	}

	for i := 0; i < n; i++ {
		if nums[i] != i {
			return i
		}
	}

	//如果0...n-1都能匹配，那缺失的数为n
	return n
}

func MissingNumber2(nums []int) int {
	//给数字增加一位，补全哈希表
	nums = append(nums, -1)
	for index, val := range nums {
		//换来的如果是无效值，直接继续
		for val != -1 && nums[index] != index && nums[val] != val {
			nums[index], nums[val] = nums[val], nums[index]
			val = nums[index]
		}
	}

	for i := range nums {
		if nums[i] != i {
			return i
		}
	}

	return -1
}
